package com.zhao.leetcode.动态规划.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: arithmetic-do-exercise
 * @author: zhaohuan
 * @create: 2025-09-07 20:32
 * @description
 * 地址：https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150
 * 题目：
 *  给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 **/
public class 最长连续序列 {

    public static void main(String[] args) {
        int[] nums = {0,3,7,2,5,8,4,6,0,1};
        System.out.println(longestConsecutive(nums));

    }



    public static int longestConsecutive(int[] nums) {

        Map<Integer, Integer> numAndTimesMap = new HashMap<>();
        int maxLen = 0;
        for (int num : nums) {
            if (numAndTimesMap.containsKey(num)) {
                continue;
            }
            int leftLen = numAndTimesMap.getOrDefault(num - 1, 0);
            int rightLen = numAndTimesMap.getOrDefault(num + 1, 0);
            int numLen = leftLen + rightLen + 1;
            maxLen = Math.max(numLen, maxLen);
            numAndTimesMap.put(num, -1);
            numAndTimesMap.put(num - leftLen, numLen);
            numAndTimesMap.put(num + rightLen, numLen);
        }
        return maxLen;
    }

    public static int longestConsecutiveByCankao(int[] nums) {
        // key表示num，value表示num所在连续区间的长度
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            // 当map中不包含num，也就是num第一次出现
            if (!map.containsKey(num)) {
                // left为num-1所在连续区间的长度，更进一步理解为：左连续区间的长度
                int left = map.getOrDefault(num - 1, 0);
                // right为num+1所在连续区间的长度，更进一步理解为：右连续区间的长度
                int right = map.getOrDefault(num + 1, 0);
                // 当前连续区间的总长度
                int curLen = left + right + 1;
                ans = Math.max(ans, curLen);
                // 将num加入map中，表示已经遍历过该值。其对应的value可以为任意值。
                map.put(num, -1);
                // 更新当前连续区间左边界和右边界对应的区间长度
                map.put(num - left, curLen);
                map.put(num + right, curLen);
            }
        }
        return ans;
    }


}
